package com.chengqs.algorithm.recursionmulti;

import org.springframework.util.StopWatch;

import java.util.LinkedList;

/**
 * 汉诺塔问题
 */
public class E02HanoiTower {
    static LinkedList<Integer> a = new LinkedList<>();
    static LinkedList<Integer> b = new LinkedList<>();
    static LinkedList<Integer> c = new LinkedList<>();

    // 3 2 1

    static void init (int n) {
        for (int i = n; i >= 1; i--) {
            a.addLast(i);
        }
    }

    /**
     * 移动 n 个盘子，从 from 到 to，借助 other
     * @param n 圆盘个数
     * @param from 源
     * @param other 暂存
     * @param to 目标
     */
    static void move(int n,
                     LinkedList<Integer> from,
                     LinkedList<Integer> other,
                     LinkedList<Integer> to) {
        if (n == 0) {
            return;
        }
        move(n - 1, from, to, other); // 把 n-1 个盘子由from,借to,移至other
        to.addLast(from.removeLast()); // 把最后的盘子由 from 移至 to
        // print();
        move(n - 1, other, from, to); // 把 n-1 个盘子由other,借from,移至to
    }

    // T(n) = 2T(n-1) + c,  O(2^64)

    public static void main(String[] args) {
        StopWatch sw = new StopWatch();
        int n = 1;
        init(n);
        print();
        sw.start("n=1");
        move(n, a, b, c);
        sw.stop();
        print();
        System.out.println(sw.prettyPrint());;
    }

    public static void print() {
        System.out.println("=========================");
        System.out.println(a);
        System.out.println(b);
        System.out.println(c);
    }
}
